package com.wz.leetcode.array;

import java.util.Arrays;

public class NextPermutation_31 {
    public static void nextPermutation(int[] nums) {
        // 找到从后往前：先上升，后下降，下降趋势里面的第一个元素
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }
        //从后往前，找到第一个比上面那个元素大的数，交换ij
        if (i >= 0) {
            int j = n - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        // 后面改为升序，这里也可以处理，从最大直接变为最小
        reverse(nums, i + 1);
    }

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

        int[] nums1 = {3, 2, 1};
        nextPermutation(nums1);
        System.out.println(Arrays.toString(nums1));

        int[] nums2 = {1, 1, 3};
        nextPermutation(nums2);
        System.out.println(Arrays.toString(nums2));

        int[] nums3 = {1, 3, 1};
        nextPermutation(nums3);
        System.out.println(Arrays.toString(nums3));

        int[] nums4 = {3, 1, 1};
        nextPermutation(nums4);
        System.out.println(Arrays.toString(nums4));
    }
}
